1. Field of the Invention
The present invention relates to a method for writing data, especially to a method for writing data into flash memory in order to improve the efficiency of operating and storage using.
2. Description of the Related Art
Flash memory is a kind of non-volatile memory. Because of low power consumption, high accessing rate, anti-shock, and light weight properties, the flash memory is widely used in computer systems and portable devices as data storage.
A common framework of flash memory storage system is as shown in FIG. 1. A flash memory 5 includes a control unit 51 and a memory unit 53. The flash memory 5 uses the control unit 51 for processing the sets of data and instructions transmitted from a host 4. After the control unit 51 receives the instructions from the host 4 and converts logical addresses to physical addresses, the memory unit 53 is then involved for data storing or reading.
Please refer to FIG. 2, the memory unit 53 is divided into several physical memory blocks (labeled PBA0 to PBAm in this embodiment, total amount: m+1). In which the physical memory block is the minimum erasable unit of the memory unit 53. In addition, every physical memory block has a plurality of physical memory pages (labeled PPA0 to PPAn in this embodiment, total amount: n+1), and the physical memory page is the minimum writable unit of the memory unit 53.
After the control unit 51 receives the instructions and the set of target data from the host 4 and converts the target logical addresses into physical addresses, an erased physical memory block in the memory unit 53 is selected (PBA0 in this example). Then, the set of target data is written into the physical memory pages of the erased physical memory block in the numerical order (PPA0, PPA1, PPA2 . . . ).
Conventional data updating process is as shown in FIG. 3. First, the control unit 51 receives a first instruction which stands for updating data. In which the first instruction indicates that the data D00 in the physical memory page PP0 of the physical memory block PBA0 in the memory unit 53 is the data to be updated. Next, the control unit 51 selects an erased physical memory block PB1 for storing the updating data D00′ transmitted from the host 4. And the control unit 51 then stores the updating data D00′ in the physical memory block PBA1 starting from the beginning of the physical memory block PBA1, that is, the physical memory page PPA0 of the physical memory block PBA1. Finally, the control unit 51 marks the data D00 in the physical memory page PPA0 of the physical memory block PBA0 as invalid data.
Then, the control unit 51 receives a second data updating instruction. In which, the second instruction indicates that the data D22 in the physical memory page PPA2 of the physical memory block PBA2 is the data to be updated. Since the physical memory block PBA1 is currently used to write new data, so the control unit 51 stores the updating data D22′ transmitted from the host 4 successively into the physical memory page PPA1 of the physical memory block PBA1. And the data D22 in the physical memory block PBA2 is then marked as invalid data.
Next, the control unit 51 receives a third data updating instruction again. Similarly, the updating data D33′ is successively stored into the physical memory page PPA2 of the currently-used physical memory block PBA1. And the data D33 stored in the physical memory page PPA3 of the physical memory block PBA3 is then marked as invalid data. The fourth data updating instruction makes the control unit 51 to store the updating data D34′ into the physical memory page PPA3 of the physical memory block PBA1, and to mark the data D34 in the physical memory page PPA4 of the physical memory block PBA3 as invalid data.
As shown in FIG. 3, the number of the physical memory pages which are marked “invalid” increases due to the data updating processes. When the storage space of the memory unit 53 reduces to a predetermined value, a garbage collection process must be carried out in order to release the physical memory pages which are occupied by the invalid data.
Please refer to FIG. 4 corresponding with FIG. 3, for explaining the garbage collection process. At the beginning, the control unit 51 chooses the physical memory block (PBA3 in this embodiment) with the most invalid physical memory pages to do the garbage collection. Then, all of the valid data D30˜D32 and D35˜D3n in the chosen physical memory block PBA3 is copied to an erased physical memory block PBA4. Next, the physical memory block PBA3 is erased for writing new data. Therefore, by doing the garbage collection, two physical memory pages are released consequently in this embodiment.
As shown in FIG. 4, the more invalid physical memory pages in the chosen physical memory block, the more physical memory pages may be released after doing the garbage collection. In the embodiment, the physical memory block PBA3 has two physical memory pages PPA3 and PPA4. So after the garbage collection, only two physical memory pages are released. Therefore, if all of the physical memory blocks in the memory unit 53 have only a few invalid physical memory pages, the efficiency of garbage collection is lowered. Moreover, the difficulty of choosing which physical memory block to do the garbage collection is increased.
Besides the above problems, the address alignment problem of data being stored is another factor which causes the garbage collection to be inefficient. Because the set of target data transmitted from the host can't always be an integer multiple of the minimum writable unit (the storage size of one physical memory page) of the memory unit 53, so it must occur that some data is not aligned to the physical memory page.
Please refer to FIG. 5A, a set of data D1 which includes data D10, D11, and D12 is going to be stored into the memory unit 53. Wherein the data D10 and D11 each is the data which can fill one physical memory page to the full. On the contrary, the data D12 is the data which is smaller than the storage size of one physical memory page (not aligned). Thus, when the control unit 51 transmits the data D12 to the memory unit 53, the data D12 is stored into the physical memory page PPA2 along with a set of old data Dd2 (or a set of dummy data) which is used to fill the physical memory page PPA2 to the full. For example, if the physical memory page PPA2 is an erased memory page, the data bits represented in the physical memory page PPA2 are all 1. So the remaining storage bits of the physical memory page PPA2 are all filled with 1.
Next, please refer to FIG. 5B, the following stored data D2 which received by the control unit 51 includes data D20, D21, D22, and D23. If the data D2 is going to be stored successively right after the data D12, then the control unit 51 copies the data D12 and combines the data D12 together with the data D20, in which the combined data can exactly fill the storage size of a physical memory page. Next, the combined data is written into the physical memory page PPA3, and the physical memory page PPA2 is marked as an invalid physical memory page.
Similarly, as shown in FIG. 5B, the data D23 can't fill the physical memory page PPA6 to the full. Therefore, the remaining storage bits of the physical memory page PPA6 are filled with the old data Ddb.
According to the above discussion, we can know that invalid physical memory page will be generated if there is a set of data wishing to be stored successively right after the not-aligned data. And if the invalid physical memory pages locate dispersedly in the memory unit 51, the storage releasing efficiency of garbage collection is not desirable.